package sword.chapter6Stack;

import java.util.Stack;

/**
 * 后缀表达式
 * <p>
 * 栈 后入先出，堆盘子一样，先取最上面的。
 * 适用于数据的保存顺序与使用顺序相反，最后保存的数据被先使用
 * <p>
 * push 入栈 插入一个
 * pop  出栈 删除栈顶，并返回数据
 * peek 取栈顶数据
 * <p>
 *
 * 栈中元素存值   待计算的数
 * 辅助的数据结构  无
 * 什么时候入栈   数字
 * 什么时候出栈   运算符
 *
 * ["2", "1", "3", "*", "+"]对应的算术表达式是“2 + 1 * 3” => 5
 *
 * @author K
 * @date 2021/12/3 16:22
 */
public class S36EvalRPN {

    public static int s37(String[] tokens) {
        Stack<Integer> stack = new Stack<Integer>();
        for (String token : tokens) {
            switch (token) {
                case "+":
                    stack.push(stack.pop() + stack.pop());
                    break;
                case "-":
                    stack.push(stack.pop() - stack.pop());
                    break;
                case "*":
                    stack.push(stack.pop() * stack.pop());
                    break;
                case "/":
                    stack.push(stack.pop() / stack.pop());
                    break;
                default:
                    stack.push(Integer.valueOf(token));
            }
        }
        return stack.peek();
    }

    public static int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<Integer>();
        for (String token : tokens) {
            switch (token) {
                case "+":
                case "-":
                case "*":
                case "/":
                    int num1 = stack.pop();
                    int num2 = stack.pop();
                    stack.push(calculate(num2, num1, token));
                    break;
                default:
                    stack.push(Integer.parseInt(token));
            }
        }

        return stack.pop();
    }

    private static int calculate(int num1, int num2, String operator) {
        switch (operator) {
            case "+":
                return num1 + num2;
            case "-":
                return num1 - num2;
            case "*":
                return num1 * num2;
            case "/":
                return num1 / num2;
            default:
                return 0;
        }
    }

    public static void main(String[] args) {
        String[] tokens = {"2", "1", "3", "*", "+"};
        int result = s37(tokens);
        int result2 = evalRPN(tokens);
        System.out.println();
    }
}
